package com.zhn;

/**
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 *
 * 示例 1：
 *
 * 输入：s = "abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 */
public class CountSubstrings {
    public static void main(String[] args) {

    }
    public  int countSubstrings(String s) {
        int res = 0;
        int m = s.length();
        boolean[][] dp = new boolean[m][m];
        //从低向上，从左到右遍历，因为dp[i][j]推断依赖于dp[i+1][j-1]
        for(int i = m-1;i >= 0;i--){
            for(int j = i;j < m;j++){
                if(s.charAt(i) == s.charAt(j)){
                   // 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
                   // 情况二：下标i 与 j相差为1，例如aa，也是回文子串,相差为2也是回文子串 aba，cac
                    if(j - i < 3){
                        res++;
                        dp[i][j] = true;
                        //情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，
                        //我们看i到j区间是不是回文子串就看aba是不是回文就可以了，
                        //那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
                    }else if (dp[i+1][j-1]) {
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        }
        return res;
    }


}
